package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * <a href="https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/">二叉树的垂序遍历(Vertical Order Traversal of a Binary Tree)</a>
 * <p>给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。</p>
 * <p>对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。</p>
 * <p>二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。</p>
 * <p>返回二叉树的 垂序遍历 序列。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *                      3
 *                    (0,0)
 *                    /   \
 *                  9      20
 *               (1,-1)   (1,1)
 *                        /  \
 *                      15    7
 *                    (2,0) (2,2)
 *
 *      输入：root = [3,9,20,null,null,15,7]
 *      输出：[[9],[3,15],[20],[7]]
 *      解释：
 *          列 -1 ：只有结点 9 在此列中。
 *          列  0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
 *          列  1 ：只有结点 20 在此列中。
 *          列  2 ：只有结点 7 在此列中。
 *
 * 示例 2：
 *                      1
 *                    (0,0)
 *                    /   \
 *                  2      3
 *               (1,-1)  (1,1)
 *                /  \   /  \
 *               4    5 6   7
 *            (2,-2) (2,0) (2,2)
 *      输入：root = [1,2,3,4,5,6,7]
 *      输出：[[4],[2],[1,5,6],[3],[7]]
 *      解释：
 *          列 -2 ：只有结点 4 在此列中。
 *          列 -1 ：只有结点 2 在此列中。
 *          列  0 ：结点 1 、5 和 6 都在此列中。
 *                    1 在上面，所以它出现在前面。
 *                    5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
 *          列  1 ：只有结点 3 在此列中。
 *          列  2 ：只有结点 7 在此列中。
 *
 * 示例 3：
 *                      1
 *                    (0,0)
 *                    /   \
 *                  2      3
 *               (1,-1)  (1,1)
 *                /  \   /  \
 *               4    6 5   7
 *            (2,-2) (2,0) (2,2)
 *      输入：root = [1,2,3,4,6,5,7]
 *      输出：[[4],[2],[1,5,6],[3],[7]]
 *      解释：
 *          这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
 *          因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>树中结点数目总数在范围 [1, 1000] 内</li>
 *         <li>0 <= Node.val <= 1000</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/2/29 16:17
 */
public class LC0987VerticalOrderTraversalOfBinaryTree_H {

    static class Solution {
        public List<List<Integer>> verticalTraversal(TreeNode root) {
            // key1：列；key2：行
            Map<Integer, List<int[]>> map = new TreeMap<>();
            process(0, 0, root, map);
            List<List<Integer>> resList = new ArrayList<>();
            for (Map.Entry<Integer, List<int[]>> entry : map.entrySet()) {
                List<int[]> value = entry.getValue();
                // 对 value 进行排序，首先根据行号升序排序；行号相同，根据value升序排列
                value.sort(((o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1]));
                List<Integer> list = new ArrayList<>();
                for (int[] val : value) {
                    list.add(val[1]);
                }
                resList.add(list);
            }
            return resList;
        }

        private void process(int row, int col, TreeNode currNode, Map<Integer, List<int[]>> map) {
            if (currNode == null) {
                return;
            }
            List<int[]> ints = map.getOrDefault(col, new ArrayList<>());
            ints.add(new int[]{row, currNode.val});
            map.put(col, ints);
            // 左子节点
            if (currNode.left != null) {
                process(row + 1, col - 1, currNode.left, map);
            }
            // 右子节点
            if (currNode.right != null) {
                process(row + 1, col + 1, currNode.right, map);
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        TreeNode root1 = new TreeNode(3);
        root1.left = new TreeNode(9);
        root1.right = new TreeNode(20);
        root1.right.left = new TreeNode(15);
        root1.right.right = new TreeNode(7);
        Printer.printListListInteger(solution.verticalTraversal(root1));

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(3);
        root2.left.left = new TreeNode(4);
        root2.left.right = new TreeNode(5);
        root2.right.left = new TreeNode(6);
        root2.right.right = new TreeNode(7);
        Printer.printListListInteger(solution.verticalTraversal(root2));

        TreeNode root3 = new TreeNode(1);
        root3.left = new TreeNode(2);
        root3.right = new TreeNode(3);
        root3.left.left = new TreeNode(4);
        root3.left.right = new TreeNode(6);
        root3.right.left = new TreeNode(5);
        root3.right.right = new TreeNode(7);
        Printer.printListListInteger(solution.verticalTraversal(root3));

        TreeNode root4 = new TreeNode(3);
        root4.left = new TreeNode(1);
        root4.right = new TreeNode(4);
        root4.left.left = new TreeNode(0);
        root4.left.right = new TreeNode(2);
        root4.right.left = new TreeNode(2);
        Printer.printListListInteger(solution.verticalTraversal(root4));
    }
}
